// 给定一个二叉树，返回它的中序 遍历。

// 示例:

// 输入: [1,null,2,3]
//    1
//     \
//      2
//     /
//    3

// 输出: [1,3,2]
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

#include <vector>
#include <stack>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归
class Solution1 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        inOrder(root, res);
        return res;
    }
    void inOrder(TreeNode* root, vector<int>& res) {
        if (!root) return;
        if (root->left) inOrder(root->left, res);
        res.push_back(root->val);
        if (root->right) inOrder(root->right, res);
    }
};

// 非递归，用栈
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        stack<TreeNode*> s{};
        TreeNode* p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            s.pop();
            res.push_back(p->val);
            p = p->right;
        }
        return res;
    }
};

/* 递归
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        inOrder(root, res);
        return res;
    }
    void inOrder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        if (root->left != nullptr) {
            inOrder(root->left, res);
        }
        res.push_back(root->val);
        if (root->right != nullptr) {
            inOrder(root->right, res);
        }
    }
};

/* 迭代，用栈
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        stack<TreeNode*> stk{};
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

/* Morris 中序遍历
Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        TreeNode* predecessor{nullptr};
        while (root != nullptr) {
            if (root->left != nullptr) {
                // predecessor节点就是当前root节点的左子树的最右节点
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                // 让predecessor的右指针指向root，继续遍历左子树
                if (predecessor->right == nullptr) {
                    predecessor->right = root;
                    root = root->left;
                } else {
                    // 说明左子树已经访问完了，我们需要断开连接
                    res.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            } else {
                // 如果没有左孩子，则直接访问右孩子
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

/* 前中后迭代统一写法
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> res{};
        stack<TreeNode*> stk{};
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            if (node != nullptr) {
                stk.pop();
                if (node->right) {
                    stk.push(node->right);
                }
                stk.push(node);
                stk.push(nullptr); // 根节点访问过，但还没处理，加入空节点做标记
                if (node->left) {
                    stk.push(node->left);
                }
            } else { // 只有遇到空节点的时候，才将下一个节点放入结果集
                stk.pop(); // 将空节点弹出
                node = stk.top();
                stk.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};